package kg.aibek.projecteuler.p10;

import java.util.ArrayList;
import java.util.List;

public class Problem24 {
	public void solve() {
		int order = 1000000;
		List<Integer> list = new ArrayList<Integer>();
		for (int i = 0; i < 10; i++) {
			list.add(i);
		}

		List<Integer> ordered = new ArrayList<Integer>();
		getFirstNumber(list, order, ordered);

		for (Integer i : ordered) {
			System.out.print(i);
		}
	}

	private void getFirstNumber(List<Integer> list, int order,
			List<Integer> ordered) {
		if (list.size() <= 1) {
			ordered.add(list.get(0));
			list.remove(0);
			return;
		}

		int step = factorial(list.size() - 1);
		int o = step;
		int pos = 0;
		while (o < order) {
			pos++;
			o += step;
		}
		ordered.add(list.get(pos));
		list.remove(pos);
		getFirstNumber(list, order - o + step, ordered);
	}

	private int factorial(int number) {
		int fact = 1;
		for (int i = 1; i <= number; i++) {
			fact *= i;
		}
		return fact;
	}

	public static void main(String[] args) {
		Problem24 p = new Problem24();
		p.solve();
	}
}
